package com.wjcxf.solution;

import com.wjcxf.struct.Point;
import com.wjcxf.struct.PopStar;

import java.util.*;
import java.util.concurrent.CountDownLatch;

/**
 * @author 我叫程晓非
 * @desc PopStarSolution
 * @date 2022-03-15
 * @version 1.0
 */
public class PopStarSolution{
    public static Object mutex = new Object();
    public static volatile long solutionCount = 0L;
    public static Stack<PopStar> popStarStack = new Stack<>();
    //用于记录最高分数的对象
    public static volatile PopStar maxScorePopStar;


    //DFS遍历所有情况
    public static List<Point> DFS(PopStar popStar){
        solutionCount = 0L;
        long beginTime =System.currentTimeMillis();
        popStarStack.push(popStar);
        maxScorePopStar = new PopStar(popStar);
        while(!popStarStack.isEmpty()){
            PopStar star = popStarStack.pop();
            List<Point> pathList = star.expansion();
            for(int i=0;i<pathList.size();i++){
                Point point = pathList.get(i);
                PopStar newPopStar = new PopStar(star);
                newPopStar.click(point.getX(),point.getY());
                if(newPopStar.checkGameOver()){
                    ++solutionCount;
                    if(newPopStar.score > maxScorePopStar.score){
                        maxScorePopStar = new PopStar(newPopStar);
                    }
                }else{
                    popStarStack.push(newPopStar);
                }
            }
        }
        long endTime = System.currentTimeMillis();
        System.out.println("检索完成");
        System.out.println("耗时:"+(endTime-beginTime)+"ms");
        System.out.println("共找到"+solutionCount+"个解决方案");
        System.out.println("最高分数为:"+maxScorePopStar.score);
        System.out.println("共"+maxScorePopStar.clickList.size()+"步");
        System.out.println("步骤为:");
        maxScorePopStar.showClickPath();
        return maxScorePopStar.clickList;
    }

    //蒙特卡洛算法
    public static List<Point> MontCarlo(PopStar popStar, int searchTime){
        solutionCount = 0L;
        maxScorePopStar = new PopStar(popStar);
        popStar.resetVisited();
        long beginTime =System.currentTimeMillis();
        List<Point> pathList =  popStar.expansion();
        List<PopStar> expansionStarList = new ArrayList<>();
        for(int i=0;i<pathList.size();++i){
            PopStar expansionStar = new PopStar(popStar);
            expansionStarList.add(expansionStar);
        }
        while(Math.abs(System.currentTimeMillis()-beginTime) <= searchTime){
            int randomIndex = ((int)(Math.random()*100))%pathList.size();

            PopStar star = expansionStarList.get(randomIndex);
            while(!star.checkGameOver()){
                List<Point> exPathList = star.expansion();
                randomIndex = ((int)(Math.random()*100))%exPathList.size();
                star.click(exPathList.get(randomIndex).getX(),exPathList.get(randomIndex).getY());
            }
            if(star.score > maxScorePopStar.score){
                maxScorePopStar = new PopStar(star);
            }
            ++solutionCount;
        }


        long endTime = System.currentTimeMillis();
        System.out.println("检索完成");
        System.out.println("耗时:"+(endTime-beginTime)+"ms");
        System.out.println("共找到"+solutionCount+"个解决方案");
        System.out.println("最高分数为:"+maxScorePopStar.score);
        System.out.println("共"+maxScorePopStar.clickList.size()+"步");
        System.out.println("步骤为:");
        maxScorePopStar.show();
        maxScorePopStar.showClickPath();
        return maxScorePopStar.clickList;
    }

    //多线程蒙特卡洛搜索算法
    //线程数量并不是越多越好，有时候越多反而越慢，因为cpu用于切换线程的开销比你计算的开销还要大了，可以设置为cpu的核心数来乘以2，可以最大程度利用cpu
    public static List<Point> MontCarloPlus(PopStar popStar,int threadNumber,final int searchTime){
        solutionCount = 0L;
        if(threadNumber <=0){
            threadNumber = 1;
        }
        if(threadNumber >16){
            threadNumber = 16;
        }
        final CountDownLatch countDownLatch = new CountDownLatch(threadNumber);
        long beginTime =System.currentTimeMillis();

        for(int i=0;i<threadNumber;i++){
            new Thread(new Runnable() {
                @Override
                public void run() {
                    maxScorePopStar = new PopStar(popStar);
                    popStar.resetVisited();
                    List<Point> pathList =  popStar.expansion();
                    List<PopStar> expansionStarList = new ArrayList<>();
                    for(int i=0;i<pathList.size();++i){
                        PopStar expansionStar = new PopStar(popStar);
                        expansionStarList.add(expansionStar);
                    }
                    while(Math.abs(System.currentTimeMillis()-beginTime) <= searchTime){
                        if(pathList.size() == 0){
                            System.out.println("continue1");
                            continue;
                        }
                        int randomIndex = ((int)(Math.random()*100))%pathList.size();

                        PopStar star = expansionStarList.get(randomIndex);
                        while(!star.checkGameOver()){
                            List<Point> exPathList = star.expansion();
                            if(exPathList.size() == 0){
                                System.out.println("continue2");
                                continue;
                            }
                            randomIndex = ((int)(Math.random()*100))%exPathList.size();
                            star.click(exPathList.get(randomIndex).getX(),exPathList.get(randomIndex).getY());

                        }
                        if(star.score > maxScorePopStar.score){
                            synchronized (mutex){
                                if(star.score > maxScorePopStar.score){
                                    maxScorePopStar = new PopStar(star);
                                }
                            }
                        }
                        ++solutionCount;
                    }
                    countDownLatch.countDown();
                }
            }).start();
        }


        try {
            countDownLatch.await();//需要捕获异常，当其中线程数为0时这里才会继续运行
        }catch (InterruptedException e){
            e.printStackTrace();
        }
        long endTime = System.currentTimeMillis();
        System.out.println("检索完成");
        System.out.println("耗时:"+(endTime-beginTime)+"ms");
        System.out.println("共找到"+solutionCount+"个解决方案");
        System.out.println("最高分数为:"+maxScorePopStar.score);
        System.out.println("共"+maxScorePopStar.clickList.size()+"步");
        System.out.println("步骤为:");

        maxScorePopStar.show();
        maxScorePopStar.showClickPath();
        return maxScorePopStar.clickList;
    }

    public static List<Point> MontCarloPlus2(PopStar popStar,int threadNumber,final int searchTime){
        solutionCount = 0L;
        if(threadNumber <=0){
            threadNumber = 1;
        }
        if(threadNumber >16){
            threadNumber = 16;
        }
        final CountDownLatch countDownLatch = new CountDownLatch(threadNumber);
        long beginTime =System.currentTimeMillis();

        for(int i=0;i<threadNumber;i++){
            new Thread(new Runnable() {
                @Override
                public void run() {
                    maxScorePopStar = new PopStar(popStar);
                    popStar.resetVisited();
                    List<Point> pathList =  popStar.expansion();
                    List<PopStar> expansionStarList = new ArrayList<>();
                    for(int i=0;i<pathList.size();++i){
                        PopStar expansionStar = new PopStar(popStar);
                        expansionStarList.add(expansionStar);
                    }
                    while(Math.abs(System.currentTimeMillis()-beginTime) <= searchTime){
                        if(pathList.size() == 0){
                            System.out.println("continue1");
                            continue;
                        }
                        int randomIndex = ((int)(Math.random()*100))%pathList.size();

                        PopStar star = expansionStarList.get(randomIndex);
                        while(!star.checkGameOver()){
                            List<Point> exPathList = star.expansion();
                            if(exPathList.size() == 0){
                                System.out.println("continue2");
                                continue;
                            }
                            randomIndex = ((int)(Math.random()*100))%exPathList.size();
                            star.click(exPathList.get(randomIndex).getX(),exPathList.get(randomIndex).getY());

                        }
                        if(star.score > maxScorePopStar.score){
                            synchronized (mutex){
                                if(star.score > maxScorePopStar.score){
                                    maxScorePopStar = new PopStar(star);
                                }
                            }
                        }
                        ++solutionCount;
                    }
                    countDownLatch.countDown();
                }
            }).start();
        }


        try {
            countDownLatch.await();//需要捕获异常，当其中线程数为0时这里才会继续运行
        }catch (InterruptedException e){
            e.printStackTrace();
        }
        //这里把结果回退9步，再使用DFS，一般还能加点分
        int oldScore = maxScorePopStar.score;
        for(int i=0;i<7;i++){
            maxScorePopStar.clickList.remove(maxScorePopStar.clickList.size()-1);
        }
        for(int i=0;i<maxScorePopStar.clickList.size();i++){
            popStar.click(maxScorePopStar.clickList.get(i).getX(),maxScorePopStar.clickList.get(i).getY());
        }
        long oldSolutionCount = solutionCount;
        DFS(popStar);
        long endTime = System.currentTimeMillis();
        System.out.println("检索完成");
        System.out.println("耗时:"+(endTime-beginTime)+"ms");
        System.out.println("共找到"+oldSolutionCount+"个解决方案");
//        System.out.println("最高分数1为:"+oldScore);
        System.out.println("最高分数为:"+maxScorePopStar.score);
        System.out.println("共"+maxScorePopStar.clickList.size()+"步");
        System.out.println("步骤为:");

        maxScorePopStar.show();
        maxScorePopStar.showClickPath();
        return maxScorePopStar.clickList;
    }


}
